package com.leetcode;

/**
 * 题目：给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 *       请你找出并返回这两个正序数组的 中位数 。
 * 假定两个数组的总长度为 totalLength，（以下说的“数组”表示两个数组合并后）
 *  >如果totalLength为奇数，则中间数为数组的第 (totalLength / 2 + 1)个数，下标为 totalLength / 2
 *  >如果为偶数，则中间数为第 (totalLength / 2)个和第 (totalLength / 2 + 1)个的平均值，对应下标减1
 * 则问题转换为 寻找数组的第 k 小的数
 *  >长度为奇数，k = totalLength / 2 + 1
 *  >长度为偶数，k = totalLength / 2 和 k = totalLength / 2 + 1。两个
 *
 * 实际操作我们并不需要将两个数组合并（利用到两个数组为正序的条件）
 * 二分查找法：
 *  判断两个个数组第 k/2 个数的大小（第 k/2 个数对应下标为 k/2 - 1 ）
 *  ①如果A[k/2 - 1] < B[k/2 - 1],则A的前k/2（包括k/2）个数可排除，因为它们肯定比第k个数小
 *  ②如果A[k/2 - 1] > B[k/2 - 1],则B的前k/2（包括k/2）个数可排除，因为它们肯定比第k个数小
 *  ③如果A[k/2 - 1] = B[k/2 - 1],则排除A的前k/2或排除B的前k/2都可以，因为它们肯定比第k个数小
 *      这里选择回到 ①
 *  ④更新：1.k值：排除 k/2 个，则 k = k - k/2;
 *        2.数组被排除几个后，数组剩下的部分当成新的数组，回到 ① 。
 *        由于我们并没有生成新的数组，可以采用定义一个下标index表示新数组的起始下标，则index初始值为0
 *        所以上面①②③中的 (k/2 - 1) 应该表示为 (index + k/2 - 1)
 *    更新完，回到 ①
 *  ⑤ 临界条件：有可能一个数组的length 比 k/2 小，只判断这个数组的最后一个元素跟另外一个数组的第 k/2 个数
 *              如果k=1，则两个更新完的数组的第一个数谁小，谁就是第 k小的数
 */
public class FindMedianSortedArrays {
    public static void main(String[] args) {
        int[] num1 = new int[]{1, 3, 4, 9};
        int[] num2 = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        double half = new Solution().findMedianSortedArrays(num1, num2);
        System.out.println("half = " + half);
    }
}
